/********************************************
 *        Fonctions de triangulation        *
 *            triangulation.h               *
 *                                          *
 *     Grivolet Alenda Bourgeois Ciabaud    *
 ********************************************/

#ifndef __SOUSGRAPHE_H__
#define __SOUSGRAPHE_H__

#include "structures.h"

/**
 * @author Bourgeois Jean-Louis
 * Cette Fonction recherche le sous-graphe 
 * maximum triangule de G.
 * @param G	Le Graphe
 * @param E	L'ensemble des sommets qui reprensente se sous-graphe
 * @return	1 si il en trouve un et place l'ensemble dans E, 0 sinon
 */
int sousGrapheMaximum( Graphe G, Ensemble *E);

int* ss( Graphe G );

Numerotation* LexBFS_SGTriangule( Graphe G );

/**
 * @author ALENDA Régis
 * @brief Teste si un sommet est quasi-simplicial dans une numérotation donnée.
 * Teste si un sommet est quasi-simplicial dans une numérotation donnée.
 * Le sommet ne doit pas être numéroté, et est considéré comme ayant un numéro plus petit que tous les autres.
 * Le tableau marque doit comporté autant d'éléments que de sommets dans le graphe, et doit être initialisé à zéro.
 * @param s Le sommet à tester.
 * @param G le graphe.
 * @param N La numérotation.
 * @param un tableau d'entier initialisé à zéro.
 * @return 1 si le sommet s est quasi simplicial dans G pour la numérotation N, 0 sinon.
 */
int quasiSimplicial( int s, Graphe G, Numerotation N, int *marque );

#endif

